\subsection{Software-architecturaal ontwerp}

De rollen van de belangrijkste componenten van het ontwerp worden eerst beschreven. Vervolgens volgt een nauwkeurigere beschrijving van elke component.

\subsubsection{Componenten}

\begin{description}
\item[Resource Agent] Elk element van het wegennet (Road of Crossroad) wordt beheerd door een bijhorende Resource Agent. Deze bezit informatie over de auto's die zich op de infrastructuur bevinden en kan schattingen maken over de verkeersdrukte op de infrastructuur in de toekomst. Daarnaast kunnen ze ook informatie verschaffen over naburige verkeerinfrastructuren.
\item[Road Agent] Een Road Agent is een Resource Agent die instaat voor het beheer van een weg.
\item[Crossroad Agent] Een Crossroad Agent is een Resource Agent die instaat voor het beheer van een kruispunt.
\item[Feasibility Ant] Feasibility Ants worden regelmatig uitgezonden door Resource Agents. Ze reizen tegen de rijrichting in en verzamelen gaandeweg informatie over de verkeersinfrastructuren die ze passeren. De verzamelde informatie wordt aan elke aangedane Resource Agent meegedeeld. Deze bouwen hiermee een beeld op van welke verkeersinfrastructuren bereikbaar zijn en hoe groot de reistijd tot elk van die infrastructuren bedraagt.
\end{description}

\begin{description}

\item[Task Agent] De besturing van elke auto wordt geregeld door een Task Agent. Deze verzamelt informatie over mogelijke paden naar de eindbestemming van de auto. Er wordt dan een optimale route uitgestippeld. Hierbij wordt ook de voorspelde verkeersdrukte in rekening gebracht. Deze geplande route wordt dan meegedeeld aan de Resource Agents.

\item[Exploration Ant] De Task Agents zenden Exploration Ants uit om informatie in te zamelen over de voorspelde reistijd tot de eindbestemming van de auto. Hiertoe verkennen ze verschillende paden tot ze de ofwel de eindbestemming bereiken ofwel een vooraf bepaald maximum aantal resources verkend hebben. Door communicatie met de Resource Agents zamelen ze de benodigde informatie in. Deze houden rekening met de verwachte verkeersdrukte. Daarna keren de ants terug naar de Task Agent en delen ze de verzamelde informatie mee.

\item[Intention Ant] Nadat een Task Agent voldoende informatie heeft ingezameld om voor een bepaalde route te kiezen, stuurt hij een Intention Ant uit langs deze route. Die verwittigt de Resource Agents dat de auto de resource zal gebruiken en reserveert de tijdsduur wanneer hij schat deze te zullen gebruiken. De auto staat dan geboekt bij de Resource Agent. Dit laat de Resource Agents ook toe om de verkeersdrukte op de resource goed te kunnen inschatten.
\end{description}

\subsubsection{Resource Agents}

Een weg is opgedeeld in verschillende segmenten, die elk leeg zijn of bezet door een auto. Een kruispunt bestaat uit \'e\'en segment. De keuze moest gemaakt worden om ofwel elk segment van een Resource Agent te voorzien, ofwel elke weg en kruispunt. De eerste optie zou voor een overdaad aan agents zorgen. Zo kan een auto op een weg alleen maar voortrijden naar het volgende segment op de weg. Een Resource Agent van een enkel segment zou dan maar weinig bruikbare informatie kunnen verschaffen. Er zou bovendien veel communicatie nodig zijn tussen de verschillende segmenten om een globaler beeld te vormen. 
Daarom is gekozen om per weg of kruispunt een Resource Agent te voorzien.

In werkelijkheid kan het gerechtvaardigd zijn om voor een lange weg meerdere Resource Agents te voorzien. Het beheer van een lange weg vereist immers meer rekenkracht en geheugen en een grotere afstand voor communicatie met naburige Resource Agents. Met het hier beschreven ontwerp moet de weg opgesplitst worden in meerdere opeenvolgende wegen, die dan elk een eigen Resource Agent hebben.\\
\\
Resource Agents bevatten een tabel met de afstanden tot alle bereikbare resources in de buurt. Deze informatie wordt hen bezorgd door Feasibility Ants. Wanneer er meerdere mogelijke routes naar eenzelfde resource zijn, wordt een rij in de tabel aangemaakt voor elke route. Elke rij heeft ook een vervaltijd. Deze kan verhoogd worden bij de aankomst van een Feasibility Ant die de route bevat. Wanneer voor een rij de vervaltijd bereikt wordt, wordt de route onderbroken verondersteld en de rij verwijderd.

\subsubsection{Task Agents}

Om starvation en deadlock te vermijden, wordt een maximum gesteld aan het aantal keer dat een auto op een kruispunt eenzelfde route plant en probeert uit te voeren, maar hierin niet slaagt. Het aantal keer dat een Task Agent een route mag proberen ligt vast in de variabele MAX\_NB\_OF\_TRIES. Als na dit aantal een Task Agent zijn auto nog niet heeft kunnen verplaatsen, zal hij de beste route langs de andere uitwegen proberen uit te voeren. Indien dit ook niet lukt, zoekt hij weer een andere route, enzovoort. Een andere mogelijkheid zou zijn om boekingen een bepaalde prioriteit te geven en deze te verhogen voor auto's die langer wachten. Dit is echter alleen een oplossing voor starvation en niet voor een deadlock.

\subsubsection{Feasibility Ants}
Een Resource Agent zendt regelmatig een Feasibility Ant uit wanneer hij reeds voor een tijd geen doorgang verleend heeft aan een Feasibility Ant. De ant beweegt zich vervolgens voort tegen de rijrichting in. Wanneer hij op een kruispunt uitkomt waar meerdere wegen op uitmonden, kloont hij zichzelf voor elk van deze wegen. 

Wanneer een Feasibility Ant bij een nieuwe Resource Agent aankomt, gebeurt het volgende: 
\begin{itemize}
 \item De Feasibility Ant vraagt de lengte van de resource op (= het aantal segmenten) en bewaart deze in een tabel. Wanneer zijn geheugen vol zit, wist hij de lengte van de oudste bewaarde resource.
 \item De ant verwittigt de Resource Agent van zijn aankomst.
 \item De Resource Agent vraagt van de Feasibility Ant op welke resources deze heeft aangedaan en de afstand tot deze resources. 
 \item De Feasibility Ant vraagt aan de Resource Agent of hij mag verdergaan. De Resource Agent staat dit toe wanneer de Feasibility Ant nieuwe informatie aanbood of oude informatie vernieuwde die op het punt stond te vervallen. Afhankelijk van het antwoord van de Resource Agent reist de ant verder of sterft hij.
\end{itemize}

Een andere mogelijkheid voor het werken met Feasibility Ants, is deze steeds geregeld uit te sturen naar naburige resources en ze na \'e\'en sprong laten sterven. Ze bevatten dan een kopie van de tabel van de Resource Agent die ze uitzendt. Het nadeel van deze techiek is dat de ants zwaarder zijn (ze bevatten meer informatie) en nieuwe informatie (over nieuwe of onderbroken wegen/kruispunten) zich trager propageert doorheen de verkeersinfrastructuur.

Wanneer Feasibility Ants tweemaal eenzelfde resource aandoen, wordt de informatie over de eerste keer (en de resources daarvoor) verwijderd uit de ant. De ant wordt (in tegenstelling tot Exploration Ants) nog wel verder gestuurd naar de volgende resources. Op deze manier kan een Feasibility Ant een lus maximaal twee keer doorlopen, met steeds minder informatie. Zo wordt elke resource op de hoogte gebracht van iedere andere resource in de lus. Met dit gedrag wordt ook voorkomen dat een rij in de tabel van de Resource Agent wordt aangemaakt voor een route die een lus bevat. De ants gaan dan ook geen oneindige lussen maken.

\subsubsection{Exploration Ants}

Een Task Agent stuurt Exploration Ants uit om de mogelijke routes te verkennen die diens bijhorende auto kan inslaan. Wanneer een Exploration Ant bij een Resource Agent aankomt, gebeurt het volgende:
\begin{itemize}
 \item De ant controleert of hij een lus gemaakt heeft. Indien dit het geval is, sterft de ant zonder terug te keren naar de Task Agent.
 \item De ant vraagt aan de Resource Agent wanneer zijn bijhorende auto de resource kan opkomen en verlaten. Hij geeft hierbij ook aan welk moment de auto ten vroegste kan aankomen bij de resource. Dit tijdstip volgt uit de verkenning die de Exploration Ant reeds gedaan heeft.
 \item De Resource Agent berekent deze informatie aan de hand van boekingen die door andere auto's gemaakt zijn en geeft deze terug aan de Exploration Ant.
 \item Indien er verschillende (niet-overlappende) tijdsintervallen zijn wanneer de resource nog vrij is, worden nieuwe Exploration Ants gemaakt voor elk van de intervallen.
 \item Elk van de Exploration Ants springt verder naar de volgende resource. Voor een kruispunt kunnen er meerdere mogelijke volgende resources zijn. In dat geval wordt voor elk van deze de Exploration Ant gekloond.
\end{itemize}

Exploration Ants hebben een hopcount: na een bepaald aantal resources te zijn voorbijgegaan, keren ze terug naar de Task Agent. Ook wanneer ze de resource met de bestemming van de auto bereiken, keren ze terug. Bij terugkeer van een Exploration Ant, vraagt de Task Agent de informatie over de verkende trip op en bewaart deze. Wanneer ze een route volgen waarlangs de bestemming niet bereikbaar is, of wanneer ze een lus hebben beschreven, sterven de ants.

Wanneer de Exploration Ants moeten terugkeren omdat de maximale hopcount bereikt werd, vragen ze eerst nog een schatting van de resterende reistijd tot de bestemming aan de Resource Agent. Deze berekent deze schatting aan de hand van de gegevens in diens tabel met afstanden tot naburige resources. Indien de bestemming hierin voorkomt, is de schatting gelijk aan de afstand tot de bestemming, verzwaard met een constante penalty voor vertraging door verkeer. Indien de bestemming niet in de tabel voorkomt, wordt naar de dichtsbijzijnde resource in vogelvlucht gezocht. De schatting wordt dan verzwaard met zowel een penalty voor vertraging door verkeer als een penalty voor vogelvlucht.

Een alternatief voor de hopcount was om de ants te laten sterven wanneer ze een bepaald aantal segmenten hadden overlopen. Dit was effici\"enter geweest voor de auto: hij verkent dan in alle richtingen even ver. Een Exploration Ant heeft echter een beperkt geheugen. Door het aantal hops vast te leggen ligt ook het geheugen van de Exploration Ant vast. Indien de Exploration Ant tot een zeker aantal segmenten zou verdergaan, zou het geheugen sterk kunnen verschillen afhankelijk van het aantal gepasseerde resources. Verder is het ook eenvoudiger een Exploration Ant het aantal hops te laten bijhouden; de ant springt namelijk van Resource Agent naar Resource Agent en niet van segment naar segment.\\
\\
Een Exploration Ant gaat in de realiteit terug via de elektronische apparaten waarlangs hij gekomen is. Om de code eenvoudig te houden, communiceert de ant hier na het be\"eindigen van diens verkenning onmiddelijk met de Task Agent vanwaar hij afkomstig is.

\subsubsection{Intention Ants}
Nadat de mogelijke routes verkend zijn met behulp van Exploration Ants, stuurt de Task Agent een Intention Ant uit langs de beste van de verkende routes. De Intention Ant boekt dan de resources langs de route zodat deze vrijgehouden zullen worden voor de auto. Mogelijk kan een Intention Ant de boeking niet vervolledigen omdat de situatie reeds veranderd is ten opzichte van deze tijdens de verkenning. Hij boekt de resources dan voor het eerstvolgende vacante moment. Het iets later boeken zal dan immers waarschijnlijk nog steeds de beste trip zijn. Indien dit toch niet zo is zullen de Exploration Ants de volgende keer toch een betere trip teruggeven en kunnen deze boekingen vervallen. 

De andere mogelijkheid zou zijn om niet te boeken. Indien dan in de volgende stap dezelfde route opnieuw geboekt moet worden, kunnen andere Intention Ants de vacante plaatsen reeds hebben ingenomen. Er moet dan mogelijk veel later geboekt worden. Ook kan dan het boeken van een trip telkens weer opnieuw falen.

De huidige resource en de eindbestemming zijn speciale gevallen. Voor de Resource Agent waar de auto zich op bevindt, moet alleen het moment van verlaten geboekt worden. In geval van een weg kan een auto de resource slechts verlaten als de auto's voor hem reeds weg zijn. Daarom krijgen bij deze boekingen steeds de auto's eerder op de weg voorrang op de auto's achter hen. Eventueel moeten dan de tijden van de auto's achter hem en de boekingen van auto's die de weg nog op moeten, opgeschoven worden naar een later tijdsstip. Omdat deze auto's de weg dan pas later kunnen verlaten, kunnen ze de volgende resources ook maar later boeken.

Wanneer een auto de resource met zijn eindbestemming moet boeken, moet hij in feite niet de hele resource boeken. Als de eindbestemming van een auto zich bijvoorbeeld in het midden van een weg bevindt, zou de weg maar tot daar gereserveerd moeten worden. De bijkomende complexiteit die dit teweeg zou brengen, weegt echter niet op tegenover de voordelen van een betere schatting. Daarom is hier gekozen om ook in dit geval de hele resource te boeken.

\subsubsection{Clock}
Er bestaat in het ontwerp \'e\'en centrale klok (het singleton Clock) waaraan de huidige tijd kan opgevraagd worden. Ze werkt met discrete tijdsintervallen. Tijdens \'e\'en kloktik kunnen alle agents hun ants uitsturen en kunnen de ants, indien nodig, terugkeren. Daarna kunnen alle Task Agents hun auto \'e\'en segment laten vooruitgaan, indien dit niet voor een botsing zou zorgen. 

In realiteit kan een centrale klok niet verwezelijkt worden. Elke agent zal dan een eigen klok hebben, die regelmatig gesynchroniseerd dient te worden. Deze synchronisatie is nodig om voldoende nauwkeurig voorspellingen in de toekomst te kunnen maken. Nu is het eenvoudiger om te werken met een centrale, discrete klok.

\subsubsection{De mainloop}
In de mainloop worden aan de agents alle ants opgevraagd en uitgevoerd, tot deze er geen meer hebben. In praktijk zullen de Task Agents dus in een eerste fase hun Exploration Ants sturen en de Resource Agents hun Feasibility Ants. De Task Agents zullen in een tweede fase hun Intention Ants sturen. Nadat alle ants terug zijn aangekomen, krijgen de Task Agents de kans een actie uit te voeren. Het alternatief was om alle Ants op hetzelfde tijdstip te zenden en de Intention Ants te baseren op de informatie van de Exploration Ants van de vorige iteratie. Aangezien de tijd dat ants bewegen te verwaarlozen is ten opzichte van de tijd dat de auto beweegt, wordt verondersteld dat de ants in twee keer uitsturen mogelijk is.